package leetcode_jz_offer.day18_sousuoAndBinTree;

/**
 * @author 美女
 * @date 2022/07/30 22:17
 **/

import java.util.HashMap;
import java.util.Map;

/**
 * 如何判断一个树root是否为平衡树：
 * 以root为根节点的二叉树左右子树的高度差<=1并且左右子树分别也都是平衡树
 */
public class Num55_II平衡二叉树 {
    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }
//    public boolean isBalanced(TreeNode root) {
//        if(root==null){
//            return true;
//        }
//        //求当前节点左右子树高度差
//        //当高度差<=1并且左右子树都是平衡二叉树即整个树是平衡二叉树
//        return Math.abs(height(root.left)-height(root.right))<=1&&isBalanced(root.left)&&isBalanced(root.right);
//    }
//    //计算树的高度
//    private int height(TreeNode node) {
//        if(node==null){
//            return 0;
//        }
//        return 1+Math.max(height(node.left),height(node.right));
//    }
    private Map<TreeNode,Integer> nodeMap=new HashMap<>();//存储结点及其对应高度
    public boolean isBalanced(TreeNode root) {
        if(root==null){
            return true;
        }
        int left=0;
        int right=0;
        if(nodeMap.containsKey(root.left)){
            //此时左树高度已经被计算过了，直接从Map中取出节点值对应高度
            left=nodeMap.get(root.left);
        }else {
            //否则，计算左子树高度，并将高度放入Map集合中
            left=height(root.left);
            nodeMap.put(root.left,left);
        }
        if(nodeMap.containsKey(root.right)){
            right=nodeMap.get(root.right);
        }else {
            right=height(root.right);
            nodeMap.put(root.right,right);
        }
        return Math.abs(left-right)<=1&&isBalanced(root.left)&&isBalanced(root.right);
    }

    private int height(TreeNode node) {
        if(node==null){
            return 0;
        }
        return 1+Math.max(height(node.left),height(node.right));
    }
}
